There is known a cryptographic technology called a secret sharing scheme for splitting secret information into a plurality of secret information shares and recovering the secret information only if the predetermined secret information shares are put together. The most famous of the available secret sharing schemes is a (k,n)-threshold secret sharing scheme (see Ad Shamir, “How to share a secret”, Comm. ACM, 22(11), 612-613 (1979) (hereinafter referred to as Document 1).
According to the (k,n)-threshold secret sharing scheme, the secret information is split into n secret information shares. The secret information can be recovered if k out of the n secret information shares are put together. The secret information cannot be recovered or any information about the secret information cannot be obtained from less than k secret information shares.
The (k,n)-threshold secret sharing scheme disclosed in Document 1 has not taken into account a cheating of persons who manage secret information shares and failures of apparatus which mange secret information shares. When an attempt is made to retrieve the secret information by merging the k secret information shares, if they include even one secret information share which is different from the original secret information shares, then the secret information cannot properly be recovered or the fact that the original secret information has not properly been recovered cannot be detected.
Martin Tompa, Heather Woll, “How to Share a Secret with Cheaters”, Journal of Cryptology, vol. 1, pages 133-138, 1988 (hereinafter referred to as Document 2), or Wakaha Ogata, Kaoru Kurosawa, Douglas R. Stinson, “Optimum Secret Sharing Scheme Secure Against Cheating”, SIAM Journal on Discrete Mathematics, vol. 20, no. 1, pages 79-95, 2006 (hereinafter referred to as Document 3) discloses a technology for detecting the fact that original secret information has not properly been recovered when an attempt is made to retrieve the secret information by merging k secret information shares including (k−1) falsified secret information shares. However, the technology disclosed in Document 2 or Document 3 fails to identify the falsified secret information shares, though it can detect the fact that the falsified secret information shares are included.
T. Rabin and M. Ben-Or, “Verifiable Secret Sharing and Multiparty Protocols with Honest Majority”, Proc. STOC '89, pp. 73-85, 1989 (hereinafter referred to as Document 4) or K. Kurosawa, S. Obana and W. Ogata, “t-Cheater Identifiable (k,n) Secret Sharing Schemes”, Proc. Crypto '95, Lecture Notes in Computer Science, vol. 963, Springer Verlag, pp. 410-423, 1995 (hereinafter referred to as Document 5) discloses a technology for identifying falsified secret information shares when secret information shares used to recover secret information include the falsified secret information shares.
According to the technology disclosed in Document 4, all t falsified secret information shares can be identified with high probability if number t of falsified secret information shares satisfies k≧2t+1 in the (k,n)-threshold secret sharing scheme.
According to the technology disclosed in Document 5, all t falsified secret information shares can be identified with high probability if number t of falsified secret information shares satisfies k≧3t+1, and the size of the secret information shares is smaller than the size of the secret information shares disclosed in Document 4.